1. Technical Field
The present invention relates to a data hiding method for hiding message data in media data and a data extraction method for extracting the hidden data.
2. Prior Art
Due to the development of multimedia-oriented society, a large amount of digitalized image and sound information is distributed over Internet or as recording media such as CD-ROMs, DVD-ROMs (or DVD-RAMs), or DVCs. Since anyone can simply make a complete copy of such digitalized information which is unlikely to be degraded, its unfair use is a problem. To prevent a third person from unfairly copying media data such as image or sound data, attention is being paid to a hiding technology that hides in original media data, information such as the sign of the author. If digitalized image data is illegally copied, the sign hidden in the copy can be checked to identify its source in order to determine whether it has been illegally made. Such a technology is called xe2x80x9cdata hidingxe2x80x9d.
FIG. 1 is a half tone image comprising digitalized data shown on a display. Photo description (messages) such as a xe2x80x9cnursexe2x80x9d, a xe2x80x9criverxe2x80x9d, a xe2x80x9ckindergarten pupilxe2x80x9d, and a xe2x80x9cbirdxe2x80x9d is hidden in the media data, that is, the digitalized image in FIG. 1(a), as shown in FIG. 1(b). Media data can be obtained by dividing an image from a photograph into small points and determining the numerical values of the brightness and color of each point. In this case, the original numerical values of the image are intentionally somewhat changed. Very small changes in the numerical values do not substantially disturb the image and are not perceived by users. This nature can be used to hide completely different information (message data) in the original image. Message data hidden in the image may include any information and may be, for example, a lattice pattern, a rule-like figure, or the sign of the producer of the image. Message data hidden in media data can be extracted by processing with a special program. Thus, based on the extracted message data, it can be determined whether the original media data has been modified.
Each of the messages shown in FIG. 1(b) is hidden near a meaningful region on the image. For example, the message xe2x80x9cbirdxe2x80x9d is hidden near the region in which the bird in the image is present, and acts as a caption. To hide a message such as information on the owner in the image, the message is preferably distributed over the image. This is because the message, which is locally hidden, may degrade the quality of that region when its amount is large. In addition, if part of the image is cut off, it is likely to be able to extract the message if it is distributed over the image. Thus, how to determine where each message piece is hidden is important. The positions are determined on the bases of a state sequence S. That is, each element of the state sequence is associated with each message and the message is hidden at the corresponding position determined on the basis of the element.
According to conventional data hiding methods, the state sequence S has been determined by a random number sequence. FIG. 2 schematically shows a layout of message data distributed on an image according to conventional methods. The image shown in FIG. 1(a) is divided into I image regions, each of which is numbered from 0 to 9. Then, message data is expressed as a message array (m), and an array element is described as an array value m[n] (0xe2x89xa6nxe2x89xa69). Each array value is associated with divided message data. Each message is hidden at the position in the image specified on the basis of the element in the state sequence S. The following equations determine a position p0 at which 0th message m[0] is hidden.
State value S0=initial value (constant)
Position p0=S0 mod Ixe2x80x83xe2x80x83[Equation 1]
The above equations indicate that after a constant has been given as the initial value of the state value S0, the remainder of I (the number of image regions) relative to the state value S0 is P0. The value of the position P0 is any integral value between 0 and (Ixe2x88x921). By associating the integral values with the order of the image regions, the message m[0] is hidden in the i-th image region. The locations Pn of the first and subsequent messages m[n] on the basis of the following equation.
Sn=Rnd(Snxe2x88x921)
Pn=Sn mod Ixe2x80x83xe2x80x83[Equation 2]
These equations indicate that the preceding state value Snxe2x88x921 is used as the seed of a random number to generate a pseudo random number array, which is used as the next state value Sn. The remainder of I relative to the state value Sn is the position Pn. The message m[n] is hidden in the image region corresponding to this value.
The hidden message can be read only by users who know the state value S0 (initial value). If the message is extracted, all the state values (S1, . . . , S9) following the state value S0 are calculated on the basis of the initial value. The positions corresponding to the state values are identified and the messages hidden at these positions are extracted.
As is seen in FIG. 2, since the state value Sn used to determine the position on the image of the n-th message m[n] depends only on the state value Snxe2x88x921 the state value Sn can be determined when the state value Snxe2x88x921 is determined. Likewise, the state value Snxe2x88x921 depends only on the state value Snxe2x88x922. By recursively repeating this procedure, all the elements (S0, S1, S2 . . . , S9) in the state sequence S can be determined. Thus, all the elements in the state sequence S depend only on the constant initially given as the initial value. Consequently, once the initial value has been identified, the state sequence S can be determined to identify all the positions of the messages distributed over the image and to extract their hidden contents.
If the initial value has been published or known to a third person despite efforts to make it secret, the third person can use the value to identify the positions of messages easily and erase the message data or write a different message data over the first data. It has been difficult for conventional methods to effectively prevent a third person from erasing the original sign to make the source unknown or writing a different sign over the original sign to act as if he or she was the author.
It is therefore an object of this invention to propose a new method for distributing and hiding message data in media data. It is another object of this invention to provide a data hiding method that prevents a third person from modifying message data.
To achieve the above objects, the present invention relates to a data hiding method of dispersively hiding the array elements of a message array in a media array based on a state value S specifying a particular array element in the media array if the media data is expressed as the media array while message data is expressed as the message array. Specifically, one aspect of the present invention comprises the steps of:
(a) determining the j-th (jxe2x89xa70) state value Sj;
(b) determining (j+1)-th state value Sj+1 based on the j-th state value, the array element of the media array indicated by the j-th state value, and the array element of the message array; and
(c) hiding data with respect to the array element of the media array indicated by the (j+1)-th state value Sj+1.
If the message array has J array elements, the above steps (a) to (c) are recursively repeated until the J array elements have been hidden. If j=0, the initial state value S0 is determined on the basis of the data in the array elements of the message array. Specifically, an initial function for determining the initial state value S0 is provided, and a value based on the data in all the elements of the message array (for example, the exclusive OR of the data) is input to this initial function.
In step (b), the (j+1)-th state value Sj+1 is determined on the basis of the exclusive OR of the j-th state value Sj, the data in the array element of the media array indicated by this state value, and the data in the array element of the message array. Specifically, a hiding position translation function is provided, and the above exclusive OR is input to this function to obtain the (j+1)-th state value Sj+1 as the output. The hiding position translation function may be, for example, a function using as a parameter, a secret key used in public-key cryptography. The hiding data may be the exclusive OR of the array element of the media array indicated by the j-th state value Sj and the array element of the message array.
In addition, a second aspect of the present invention relates to a data extraction method of extracting a message array from a media array based on a state value specifying a particular array element in the media array if the message data is expressed as the message array and if hiding data including the message data is expressed as a hiding array while the media data in which the hiding data is dispersively hidden is expressed as the media array. This aspect of the present invention comprises the steps of:
(a) determining the j-th (jxe2x89xa71) state value Sj;
(b) extracting an array elements of the hiding array from the array element of the media array indicated by the j-th state value Sj;
(c) determining the (jxe2x88x921) state value Sjxe2x88x921 based on the j state value Sj and the extracted array element of the hiding array; and
(d) extracting an array element of the message array based on the array element of the media array indicated by the (jxe2x88x921)-th state value Sjxe2x88x921 and the extracted array element of the hiding array.
The steps (a) to (c) are recursively repeated until a extraction finish condition has been met. In step (a), the state value Sj used to start extraction is provided beforehand to an extractor as information required for extraction. The state value Sj may be, for example, the last state value generated when the message array was hidden. In step (c), the (jxe2x88x921) state value Sjxe2x88x921 is determined on the basis of the exclusive OR of the j-th state value Sj and the data in an array element of the hiding array. The array element of the hiding array is extracted from the array element of the media array indicated by the j-th state value Sj. In addition, an extraction position translation function may be provided beforehand, and in step (c), the exclusive OR of the j-th state value Sj and the data in the array element of the hiding array may be input to this function to obtain the (jxe2x88x921)-th state value Sjxe2x88x921 as the output. The extraction position translation function may be, for example, a deciphering function using as a parameter, a secret key used in an enciphering key method. In step (b), the array element of the hiding array is be the exclusive OR of the array element of the media array indicated by the (jxe2x88x921)-th state value Sjxe2x88x921 the array element of the media array, and the array element of the message array.
In addition, a third aspect of the subject invention provides a data hiding method of hiding message data in media data, comprising the steps of (a) identifying one block (a pixel block in image data) in the media data in which the message data is to be hidden, (b) determining the characteristic value (for example, a pixel, brightness, or variance value) of the identified block, and (c) manipulating the characteristic value of the block so as to hide the message data by referencing a translation rule that associates the contents of the data to be hidden with the difference between a reference value for the characteristic value and the characteristic value of the block.
The reference value may be the characteristic value of another block present in the media data. If the first and second blocks are identified in the media data, these blocks are paired and the characteristic value of each pair is determined. The characteristic values obtained are compared and manipulated on the basis of the translation rule (for example, by exchanging the characteristic values) so as to hide the message data. If the message data comprises a plurality of bits, the steps (a) to (c) are repeated.
Still further, a fourth aspect of the present invention provides a data extraction method of extracting message data from media data in which the message data is hidden, comprising the steps of (a) identifying one block in the media data in which the message data is hidden, (b) determining the characteristic value of the identified block, and (c) extracting the hidden message data according to the characteristic value of the block by referencing a translation rule that associates the contents of the data to be extracted with the difference between a reference value for the characteristic value and the characteristic value of the block.
The reference value may be the characteristic value of another block present in the media data. If the first and second blocks are identified in the media data, these blocks are paired and the characteristic value of each pair is determined. Then, the hidden message data is extracted according to the characteristic value of each block by referencing the translation rule that associates the contents of data to be extracted with the difference in the characteristic values of the blocks. If the characteristic value of the first block is larger than that of the second block, this translation rule extracts one of the bits, and otherwise, extracts the other bit.
A further embodiment of the present invention relates to a system for implementing the above data extraction method. That is, the present invention further provides a data extraction system for extracting message data from media data in which the message data is hidden, comprising a translation means for translating the media data in which the message is hidden, into digital signals, the media data being transmitted as analog signals; an identification means for identifying one block in the media data in which the message data is hidden, the media data being transmitted as the output of the translation means; a characteristic value calculation means for determining the characteristic value of the block identified by the identification means; a storage means for storing a translation rule that associates the contents of data to be extracted with the difference between a reference value for the characteristic value and the characteristic value of the block; and an extraction means for extracting the hidden message data according to the characteristic value of the block.
Furthermore, the present invention also relates to a semiconductor integrated circuit with the functions of the above data extraction system provided on a single chip. That is, the present invention provides a semiconductor integrated circuit for extracting message data from media data in which the message data is hidden, comprising a means for determining a characteristic value of one block identified as the one in which the message data is hidden; and an extraction means for extracting the hidden message data according to the characteristic value of the block by referencing a translation rule that associates the contents of data to be extracted with the difference between a reference value for the characteristic value and the characteristic value of the block.